'''
倍增算法
'''

def build_suffix_array(s):
    n = len(s)
    sa = [i for i in range(n)]
    rank = [ord(s[i]) for i in range(n)]
    k = 1
    while k < n:
        tmp = [(rank[i], rank[(i + k) % n], i) for i in range(n)]
        tmp.sort()
        rank[sa[0]] = 0
        for i in range(1, n):
            if tmp[i][0] == tmp[i - 1][0] and tmp[i][1] == tmp[i - 1][1]:
                rank[sa[i]] = rank[sa[i - 1]]
            else:
                rank[sa[i]] = rank[sa[i - 1]] + 1
        if rank[sa[n - 1]] == n - 1:
            break
        k *= 2
        for i in range(n):
            sa[i] = (sa[i] - k + n) % n
        tmp_rank = rank.copy()
        for i in range(n):
            second_key = (sa[i] + k) % n
            rank[sa[i]] = (tmp_rank[sa[i]], tmp_rank[second_key])
    return sa


'''
dc3
'''
def sort_by_first(s, group):
    n = len(s)
    cnt = [0] * (n + 1)
    for x in group:
        cnt[x] += 1
    for i in range(1, n + 1):
        cnt[i] += cnt[i - 1]
    res = [0] * n
    for i in range(n - 1, -1, -1):
        x = group[i]
        res[cnt[x] - 1] = i
        cnt[x] -= 1
    return res


def induced_sort(s, group, sa12):
    n = len(s)
    sa = [-1] * n
    cnt = [0] * (n + 1)
    for x in sa12:
        cnt[x[2] + 1] += 1
    for i in range(1, n + 1):
        cnt[i] += cnt[i - 1]
    for i in range(len(sa12) - 1, -1, -1):
        x = sa12[i]
        j = cnt[x[2] + 1] - 1
        sa[j] = x[2]
        cnt[x[2] + 1] -= 1
    cnt = [0] * (n + 1)
    for i in range(n):
        if sa[i] >= 1 and s[sa[i] - 1] == '2':
            x = group[sa[i] - 1] + 1
            cnt[x] += 1
    for i in range(1, n + 1):
        cnt[i] += cnt[i - 1]
    for i in range(len(sa) - 1, -1, -1):
        j = sa[i]
        if j >= 1 and s[j - 1] == '2':
            x = group[j - 1] + 1
            sa[cnt[x] - 1] = j - 1
            cnt[x] -= 1
    cnt = [0] * (n + 1)
    for i in range(n):
        if sa[i] >= 1 and s[sa[i] - 1] == '1':
            x = group[sa[i] - 1] + 1
            cnt[x] += 1
    for i in range(1, n + 1):
        cnt[i] += cnt[i - 1]
    for i in range(n - 1, -1, -1):
        if sa12[i] >= n / 2:
            continue
        j = sa12[i] * 3 + 1
        if j >= n:
            continue
        j = group[j]
        sa[cnt[j]] = sa12[i] * 3 + 1
        cnt[j] += 1
    cnt = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        if sa[i] >= 1 and s[sa[i] - 1] == '0':
            x = group[sa[i] - 1] + 1
            cnt[x] += 1
    for i in range(1, n + 1):
        cnt[i] += cnt[i - 1]
    for i in range(n - 1, -1, -1):
        if sa[i] >= 1 and s[sa[i] - 1] == '0':
            x = group[sa[i] - 1] + 1
            sa[cnt[x] - 1] = sa[i] - 1
            cnt[x] -= 1
    return sa


def build_suffix_array(s):
    n = len(s)
    if n == 1:
        return [0]
    if n == 2:
        if s[0] < s[1]:
            return [0, 1]
        else:
            return [1, 0]
    if n == 3:
        if s == 'aba':
            return [0, 2, 1]
        else:
            return [1, 2, 0]
    s12 = [i for i in range(n) if i % 3 != 0]
    s12.append(0)
    s12.sort(key=lambda x: (s[x], s[x + 1], s[x + 2]))
    group = [0] * n
    new_group = [0] * n
    group[s12[0]] = 0
    for i in range(1, len(s12)):
        if s[s12[i]] != s[s12[i - 1]] or s[s12[i] + 1] != s[s12[i - 1] + 1] or s[s12[i] + 2] != s[s12[i - 1] + 2]:
            group[s12[i]] = group[s12[i - 1]] + 1
        else:
            group[s12[i]] = group[s12[i - 1]]
    if group[s12[-1]] == len(s12) - 1:
        new_sa12 = s12
    else:
        new_s12 = [group[i] for i in s12]
        new_sa12 = build_suffix_array(new_s12)
        new_sa12 = [s12[i] for i in new_sa12]
    new_s = [group[i] for i in range(n) if i % 3 != 0]
    new_sa = induced_sort(s, group, [(new_sa12[i] // 3,
                                      (new_sa12[i] % 3, new_sa12[i] + 1 < n and group[new_sa12[i] + 1] or 0),
                                      new_sa12[i] % 3 == 1 and s[new_sa12[i] + 2] or s[new_sa12[i]]) for i in
                                     range(len(new_sa12))])
    res = [0] * n
    j = 0
    k = 0
    for i in range(n):
        if new_sa[j] % 3 == 1:
            if s[new_sa[j]] != s[k] or s[new_sa[j] + 1] != s[k + 1] or s[new_sa[j] + 2] != s[k + 2]:
                res[i] = new_sa[j]
            else:
                res[i] = k
            j += 1
            if j == len(new_sa):
                res[i + 1:] = [new_sa[k] + 1 for k in range(i + 1, n)]
                break
        else:
            if s[new_sa[j]] != s[k] or s[new_sa[j] + 1] != s[k + 1]:
                res[i] = new_sa[j]
            else:
                res[i] = k
            j += 1
            if j == len(new_sa):
                res[i + 1:] = [new_sa[k] + 1 for k in range(i + 1, n)]
                break
        k = res[i]
    return res
